package hot100;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class topKFrequent {
    public int[] topKFrequent(int[] nums, int k) {
        //hash表存储每个数字及其次数，小根堆来放置前k个高频元素
        Map<Integer,Integer> hash = new HashMap<>();

        PriorityQueue<Integer> que = new PriorityQueue();

        for(int x:nums) {
            if(!hash.containsKey(x)) {//新元素
                hash.put(x,hash.getOrDefault(x,0)+1);
                if(k > 0) {//堆没有满，添加新元素
                    que.offer(x);

                }else{//堆满了,比较新元素和堆顶元素的出现次数
                    if(hash.get(que.peek()) < hash.get(x)) {//新元素频次高于堆顶，弹出堆顶，放置新元素
                        que.poll();
                        que.offer(x);
                    }
                }
            }else {
                hash.put(x,hash.get(x)+1);
                if(hash.get(que.peek()) < hash.get(x)) {//新元素频次高于堆顶，弹出堆顶，放置新元素
                    que.poll();
                    que.offer(x);
                }
            }

        }
        int[] ret = new int[k];
        int i = 0;
        if(!que.isEmpty()) {
            ret[i] = que.poll();
            i++;
        }
        return ret;
    }
}
